package com.dzsw.datastruct.tree.binary;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import java.util.LinkedList;
import java.util.Queue;

public abstract class AbstractBinaryTreeImpl<E> implements IBinaryTree<E> {

    private static Logger logger = LogManager.getLogger(AbstractBinaryTreeImpl.class);
    /**
     * 树节点的数量
     */
    protected int size;
    /**
     * 根节点
     */
    protected Node<E> root;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public void clear() {
        this.root = null;
        this.size = 0;
    }

    @Override
    public boolean isComplete() {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) {
                return false;
            }

            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            } else if (node.getRight() != null) {
                return false;
            }

            if (node.getRight() != null) {
                queue.offer(node.getRight());
            } else {
                leaf = true;
            }
        }
        return true;
    }

    @Override
    public boolean isProper() {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }

            if (node.getRight() != null) {
                queue.offer(node.getRight());
            }
            // 意味着将要访问下一层
            if (levelSize == 0) {
                // 每一层访问完成后，下一层的节点个数是队列的 size
                levelSize = queue.size();
                if (levelSize % 2 != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    @Override
    public void levelOrder(Visitor<E> visitor) {
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.isStop()) {
                return;
            }
            visitor.setStop(visitor.visit(node.getElement()));
            // 如果有左子树，入队
            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }
            // 如果有右子树，入队
            if (node.getRight() != null) {
                queue.offer(node.getRight());
            }
        }
    }

    @Override
    public String toString() {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        StringBuilder builder = new StringBuilder();
        toString(this.root, builder, "");
        return builder.toString();
    }

    /**
     * 获取传入节点的前驱节点
     *
     * @param node
     * @return
     */
    @Override
    public Node<E> predecessor(Node<E> node) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        // 前驱节点在左子树当中（left.right.right.right.right...）
        Node<E> p = node.getLeft();
        if (p != null) {
            while (p.getRight() != null) {
                p = p.getRight();
            }
            return p;
        }
        // 从父节点、祖父节点中查询前驱节点
        while (node.getParent() != null && node == node.getRight().getLeft()) {
            node = node.getParent();
        }
        return node.getParent();
    }

    /**
     * 获取传入节点的后继节点
     *
     * @param node
     * @return
     */
    @Override
    public Node<E> successor(Node<E> node) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        // 前驱节点在左子树当中（right.left.left.left....）
        Node<E> p = node.getRight();
        if (p != null) {
            while (p.getLeft() != null) {
                p = p.getLeft();
            }
            return p;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.getParent() != null && node == node.getParent().getRight()) {
            node = node.getParent();
        }
        return node.getParent();
    }

    /**
     * 中序遍历，树状打印二叉树
     * @param node
     * @param builder
     * @param prefix
     */
    private void toString(Node<E> node, StringBuilder builder, String prefix) {
        if (node == null) {
            return;
        }
        toString(node.getLeft(), builder, prefix + "L->");
        builder.append(prefix).append(node.getElement()).append("\n");
        toString(node.getRight(), builder, prefix + "R->");
    }

    @Override
    public abstract void preOrder(Visitor<E> visitor);

    @Override
    public abstract void inOrder(Visitor<E> visitor);

    @Override
    public abstract void postOrder(Visitor<E> visitor);

    @Override
    public abstract int height();
}
